// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-08 00:30
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LeafSimilar {
    /**
     * 存储叶子节点集合
     */
    List<Integer> leaf = new ArrayList<>();

    /**
     * 判断两棵二叉树是否叶相似
     * 根据二叉树遍历叶子节点的顺序不会改变，在遍历中存储叶子节点的信息再进行比较
     */
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        preOrder(root1);
        preOrder(root2);
        int n = leaf.size() / 2;
        for (int i = 0; i < n; i++) {
            if (leaf.get(i) - leaf.get(n + i) != 0) {
                return false;
            }
        }
        System.out.println(n);
        return leaf.size() % 2 == 0;
    }

    private void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leaf.add(root.val);
        }

        if (root.left != null) {
            preOrder(root.left);
        }
        if (root.right != null) {
            preOrder(root.right);
        }
    }
}
